πŸ’‘ μ•Œκ³ λ¦¬μ¦˜ 뢄석

@Seongukbaek Posted March 28, 2022 Β· Updated March 28, 2022 Β· 26 min read

[ν”„λ‘œκ·Έλž˜λ° λŒ€νšŒμ—μ„œ λ°°μš°λŠ” μ•Œκ³ λ¦¬μ¦˜ 문제 ν•΄κ²° μ „λž΅ - κ΅¬μ’…λ§Œ]을 읽고 μ •λ¦¬ν•œ POSTμž…λ‹ˆλ‹€.

πŸ’‘ κ°œκ΄€

μ–΄λ–€ μž‘μ—…μ΄ μ£Όμ–΄μ‘Œμ„ λ•Œ 컴퓨터가 이 μž‘μ—…μ„ ν•΄κ²°ν•˜λŠ” 방법을 μ•Œκ³ λ¦¬μ¦˜μ΄λΌκ³  ν•œλ‹€. 또 λ‹€λ₯΄κ²ŒλŠ”, 같은 일을 ν•˜λŠ” μ—¬λŸ¬ κ°€μ§€μ˜ 방법이 μ‘΄μž¬ν•œλ‹€. μ΄λ•Œ μ£Όμ–΄μ§„ 문제λ₯Ό ν•΄κ²°ν•˜λŠ” ν•œ κ°€μ§€ 방법을 λͺ…λ£Œν•˜κ²Œ 써놓은 것을 μ•Œκ³ λ¦¬μ¦˜μ΄λΌκ³  ν•œλ‹€.

μ΄λŸ¬ν•œ μΈ‘λ©΄μ—μ„œ, μ£Όκ΄€μ μ΄κ±°λ‚˜ λͺ¨ν˜Έν•œ 것은 μ•Œκ³ λ¦¬μ¦˜μ΄λΌκ³  ν•  수 μ—†λ‹€. "μ„œμšΈ μ‹ μ΄Œμ—­μ—μ„œ μΆ˜μ²œμ— κ°„λ‹€." λΌλŠ” μ˜ˆμ‹œλ₯Ό λ“€μ—ˆμ„ λ•Œ, λ‹€μŒμ€ μ •λ‹Ήν•œ μ•Œκ³ λ¦¬μ¦˜μ΄λΌκ³  ν•  수 μžˆλ‹€.

  1. μ§€ν•˜μ²  2ν˜Έμ„ μ„ 타고 μ‹œμ²­μ—­μœΌλ‘œ κ°„λ‹€.
  2. μ§€ν•˜μ²  1ν˜Έμ„ μœΌλ‘œ κ°ˆμ•„νƒ€κ³  μ²­λŸ‰λ¦¬μ—­μœΌλ‘œ κ°„λ‹€.
  3. κ²½μΆ˜μ„ μ„ 타고, μΆ˜μ²œμ—­μ—μ„œ λ‚΄λ¦°λ‹€.

ν•˜μ§€λ§Œ λ‹€μŒμ˜ κ²½μš°λŠ” 맀우 주관적이며, λ”°λΌμ„œ 본질적으둜 λͺ¨ν˜Έν•˜κΈ°μ— μ•Œκ³ λ¦¬μ¦˜μ΄λΌκ³  ν•  수 μ—†λ‹€.

  1. 강동ꡬ μͺ½μœΌλ‘œ κ°€λŠ” λ²„μŠ€λ₯Ό 탄닀.
  2. λ™μ„œμšΈ λ²„μŠ€ 터미널 κ·Όμ²˜μ— 온 것 κ°™μœΌλ©΄ λ‚΄λ¦°λ‹€.
  3. 좘천 μͺ½μœΌλ‘œ κ°€λŠ” λ²„μŠ€λ₯Ό 타고, ν•œμ°Έ κ°€λ‹€ λ‚΄λ¦°λ‹€.

ν•œ 문제λ₯Ό ν•΄κ²°ν•˜λŠ” 데 μ—¬λŸ¬ 개의 μ•Œκ³ λ¦¬μ¦˜μ΄ μžˆμ„ 수 μžˆλ‹€. κ·Έλ ‡λ‹€λ©΄ μ–΄λ– ν•œ μ•Œκ³ λ¦¬μ¦˜μ„ λ§Œλ“€μ–΄μ•Ό ν• κΉŒ? μ•Œκ³ λ¦¬μ¦˜μ— λŒ€ν•œ 평가 기쀀은 "μ‹œκ°„"κ³Ό "곡간"이 μžˆλ‹€.

  • μ‹œκ°„

    • μ•Œκ³ λ¦¬μ¦˜μ΄ 적은 μ‹œκ°„μ„ μ‚¬μš©ν•œλ‹€ = 더 λΉ λ₯΄κ²Œ λ™μž‘ν•œλ‹€
    • μ•Œκ³ λ¦¬μ¦˜μ˜ μˆ˜ν–‰ 속도와 νŠΉμ„±μ„ λΆ„μ„ν•˜λŠ” λŠ₯λ ₯을 λ°°μ–‘ν•  ν•„μš”κ°€ μžˆλ‹€.
  • 곡간

    • μ•Œκ³ λ¦¬μ¦˜μ΄ 적은 곡간을 μ‚¬μš©ν•œλ‹€ = 더 적은 μš©λŸ‰μ˜ λ©”λͺ¨λ¦¬λ₯Ό μ‚¬μš©ν•œλ‹€
    • 이둠적으둜 아무리 λΉ λ₯΄λ”라도 λ„ˆλ¬΄ λ§Žμ€ λ©”λͺ¨λ¦¬ 곡간을 μš”κ΅¬ν•œλ‹€λ©΄ μˆ˜ν–‰ν•  수 없을 것이닀.

두 평가 기쀀은 μ„œλ‘œ μƒμΆ©λ˜μ–΄ tradeoffλ₯Ό λ°œμƒμ‹œν‚€λŠ” κ²½μš°κ°€ λ§Žλ‹€. 이후에 λ‚˜μ˜¬ μ•Œκ³ λ¦¬μ¦˜λ“€μ—μ„œ 닀루도둝 ν•œλ‹€.


πŸ’‘ μ•Œκ³ λ¦¬μ¦˜μ˜ μ‹œκ°„ λ³΅μž‘λ„ 뢄석

πŸ” λ„μž…

μ’€ 더 λΉ λ₯Έ μ•Œκ³ λ¦¬μ¦˜μ„ λ§Œλ“€κΈ° μœ„ν•΄μ„œλŠ” μ•Œκ³ λ¦¬μ¦˜μ˜ 속도λ₯Ό μ–΄λ–»κ²Œ 츑정할지에 λŒ€ν•œ 기쀀을 μ •ν•΄μ•Ό ν•œλ‹€. κ°€μž₯ 직관적인 방법은 "각각을 ν”„λ‘œκ·Έλž¨μœΌλ‘œ κ΅¬ν˜„ν•œ λ’€ 같은 μž…λ ₯에 λŒ€ν•΄ 두 ν”„λ‘œκ·Έλž¨μ˜ μˆ˜ν–‰ μ‹œκ°„μ„ μΈ‘μ •ν•˜λŠ” 것"이닀. μ‹€κ΅¬ν˜„ μ‹œ μ‚¬μš©μžκ°€ λŠλΌκΈ°μ— λ„ˆλ¬΄ λŠλ¦¬λ‹€λ©΄ μ†Œμš©μ΄ μ—†κΈ° λ•Œλ¬Έμ— ν˜„μ‹€μ μœΌλ‘œλ„ μœ μš©ν•œ 방법 쀑 ν•˜λ‚˜μ΄λ‹€.

ν•˜μ§€λ§Œ "ν”„λ‘œκ·Έλž¨μ˜ μ‹€ν–‰ μ‹œκ°„μ€ μ•Œκ³ λ¦¬μ¦˜μ˜ 속도λ₯Ό 일반적으둜 μ΄μ•ΌκΈ°ν•˜λŠ” 기쀀이 λ˜κΈ°μ—λŠ” 뢀적합"ν•˜λ‹€.

  • ν”„λ‘œκ·Έλž¨μ˜ μˆ˜ν–‰ μ‹œκ°„μ€ μ‚¬μš©ν•œ ν”„λ‘œκ·Έλž˜λ° μ–Έμ–΄, ν•˜λ“œμ›¨μ–΄λŠ” 물둠이고 운영체제, μ»΄νŒŒμΌλŸ¬κΉŒμ§€ μˆ˜λ§Žμ€ μš”μ†Œμ— μ˜ν•΄ λ°”λ€” 수 있기 λ•Œλ¬Έμ΄λ‹€.
  • ν”„λ‘œκ·Έλž¨μ˜ μ‹€μ œ μˆ˜ν–‰ μ‹œκ°„μ΄ λ‹€μ–‘ν•œ μž…λ ₯에 λŒ€ν•œ μ‹€ν–‰ μ‹œκ°„μ„ λ°˜μ˜ν•˜μ§€ λͺ»ν•˜λŠ” λ¬Έμ œλ„ μžˆλ‹€.

    • μ•Œκ³ λ¦¬μ¦˜μ€ μ–Έμ œλ‚˜ 같은 μ†λ„λ‘œ λ™μž‘ν•˜λŠ” 것이 μ•„λ‹ˆλ©°, μž…λ ₯의 ν¬κΈ°λ‚˜ νŠΉμ„±μ— 따라 μˆ˜ν–‰ μ‹œκ°„μ΄ λ‹¬λΌμ§ˆ 수 μžˆλ‹€.

반볡문이 μ§€λ°°ν•œλ‹€
μžλ™μ°¨ 2λŒ€κ°€ 있고, μ„œμšΈμ—μ„œ λΆ€μ‚°κΉŒμ§€ κ°€λ €κ³  ν•  λ•Œ μ–΄λŠ μžλ™μ°¨λ₯Ό 타야 빨리 도착할 수 μžˆμ„μ§€ μ•Œκ³  μ‹Άλ‹€. μ•„λž˜λŠ” μžλ™μ°¨μ— λŒ€ν•œ 정보이닀.

ν•­λͺ© μžλ™μ°¨A μžλ™μ°¨B
μ‹œλ™ κ±°λŠ”λ° κ±Έλ¦¬λŠ” μ‹œκ°„ 3λΆ„ 5초
λ¬Έ μ—΄μ—ˆλ‹€ λ‹«λŠ” 데 κ±Έλ¦¬λŠ” μ‹œκ°„ 1λΆ„ 0초
μš΄μ „μ„ 등받이 μ‘°μ ˆμ— κ±Έλ¦¬λŠ” μ‹œκ°„ 5λΆ„ 0초
μ•ž 유리 λ‹¦λŠ”λ° κ±Έλ¦¬λŠ” μ‹œκ°„ 4λΆ„ 0초
μ΅œλŒ€ μ‹œμ† 200km/h 40km/h

사싀 μžλ™μ°¨ BλŠ” μžμ „κ±°μ΄λ‹€. μ‹œλ™ κ±°λŠ”λ° κ±Έλ¦¬λŠ” μ‹œκ°„μ„ μ œμ™Έν•˜κ³ λŠ” λ‹€λ₯Έ 뢀가적인 μ‹œκ°„λ“€μ΄ ν•„μš”μ—†μ§€λ§Œ, κ·Έλ ‡λ‹€κ³  ν•΄μ„œ μžμ „κ±°λ₯Ό 타고 μ„œμšΈμ—μ„œ λΆ€μ‚°κΉŒμ§€ κ°€λ €λŠ” μ‚¬λžŒμ€ λ³„λ‘œ 없을 것이닀.

  • 였래 κ±Έλ¦¬λŠ” ν•­λͺ©λ“€μ€ 사싀 μΆœλ°œν•  λ•Œ ν•œ 번만 μ μš©λ˜λŠ” 반면, μ΅œλŒ€ μ‹œμ†μ€ λ‹¬λ¦¬λŠ” λ‚΄λ‚΄ 적용되기 λ•Œλ¬Έμ΄λ‹€.

μ΄λ ‡κ²Œ ν•œ κ°€μ§€ ν•­λͺ©μ΄ μ „μ²΄μ˜ λŒ€μ†Œλ₯Ό μ’Œμ§€μš°μ§€ν•˜λŠ” 것을 "μ§€λ°°ν•œλ‹€(dominate)"라고 ν‘œν˜„ν•œλ‹€.

그럼 μ•Œκ³ λ¦¬μ¦˜μ—μ„œ μˆ˜ν–‰ μ‹œκ°„μ„ μ§€λ°°ν•˜λŠ” 것은 λ¬΄μ—‡μΌκΉŒ? λ°”λ‘œ λ°˜λ³΅λ¬Έμ΄λ‹€.

  • μž…λ ₯에 상관없이 항상 같은 μˆ˜ν–‰ μ‹œκ°„μ„ κ°–λŠ” μ•Œκ³ λ¦¬μ¦˜λ„ μžˆμ§€λ§Œ, λŒ€κ°œ μž…λ ₯ 크기에 따라 μˆ˜ν–‰ νšŸμˆ˜κ°€ μ •ν•΄μ§€λŠ” 반볡문이 있기 λ§ˆλ ¨μ΄λ‹€.

    • μž…λ ₯이 μž‘μ„ 수둝 반볡 μ™Έμ˜ λ‹€λ₯Έ μš”μ†Œλ“€μ˜ 비쀑이 클 수 μžˆμ§€λ§Œ, μž…λ ₯이 컀질 수둝 반볡문이 μ•Œκ³ λ¦¬μ¦˜μ˜ μˆ˜ν–‰ μ‹œκ°„μ„ μ§€λ°°ν•˜κ²Œ λœλ‹€.

λ”°λΌμ„œ, λŒ€κ°œ μ•Œκ³ λ¦¬μ¦˜μ˜ μˆ˜ν–‰ μ‹œκ°„μ„ 반볡문이 μˆ˜ν–‰λ˜λŠ” 횟수둜 μΈ‘μ •ν•œλ‹€. (μž…λ ₯의 크기에 λŒ€ν•œ ν•¨μˆ˜λ‘œ ν‘œν˜„)

μ•„λž˜λŠ” μ£Όμ–΄μ§„ λ°°μ—΄μ—μ„œ κ°€μž₯ 많이 λ“±μž₯ν•˜λŠ” 수λ₯Ό μ°ΎλŠ” μ½”λ“œμ΄λ‹€. μˆ˜ν–‰ μ‹œκ°„μ€ λ°°μ—΄μ˜ 크기 N 에 λ”°λΌμ„œ λ³€ν•œλ‹€. N 번 μˆ˜ν–‰λ˜λŠ” 반볡문이 두 개 κ²Ήμ³μžˆμ–΄ 반볡문의 κ°€μž₯ μ•ˆμͺ½μ€ 항상 N^2 번 μ‹€ν–‰λ˜κ³ , λ”°λΌμ„œ 이 μ•Œκ³ λ¦¬μ¦˜μ˜ μˆ˜ν–‰ μ‹œκ°„μ€ N^2 이닀.

private static int majority(int[] array) { int N = array.length; int majority = -1, majorityCnt = 0; for (int i = 0; i < N; i++) { // array에 λ“±μž₯ν•˜λŠ” μš”μ†Œμ˜ 수λ₯Ό μ„Όλ‹€. int V = array[i], cnt = 0; for (int j = 0; j < N; j++) { if (V == array[j]) cnt++; } // μ§€κΈˆκΉŒμ§€μ˜ μ΅œλŒ€ λΉˆλ„μ™€ 비ꡐ ν›„ μ΅œμ‹ ν™” if (cnt > majorityCnt) { majorityCnt = cnt; majority = V; } } return majority; }

λ§Œμ•½ μž…λ ₯으둜 μ£Όμ–΄μ§€λŠ” μˆ«μžλ“€μ˜ λ²”μœ„κ°€ μž‘λ‹€λ©΄, 배열을 μ΄μš©ν•΄ 각 μˆ«μžκ°€ λ“±μž₯ν•˜λŠ” 횟수λ₯Ό μ‰½κ²Œ μ…€ 수 있고, λ§ˆμ§€λ§‰μ— λΉˆλ„μˆ˜ 배열을 μˆœνšŒν•˜λ©΄μ„œ μ΅œλŒ€μΉ˜μ˜ μœ„μΉ˜λ₯Ό 찾으면 λœλ‹€. μ•„λž˜ μ½”λ“œκ°€ 이λ₯Ό κ΅¬ν˜„ν–ˆλ‹€.

private static int majority2(int[] array) { int N = array.length; int[] frequency = new int[101]; for (int j : array) { frequency[j]++; } int majority = 0; for (int i = 1; i <= 100; i++) { if (frequency[i] > frequency[majority]) majority = i; } return majority; }
  • 반볡문이 2κ°œκ°€ μžˆλ‹€. ν•˜λ‚˜λŠ” N 번 μˆ˜ν–‰λ˜κ³ , ν•˜λ‚˜λŠ” 100번 μˆ˜ν–‰λœλ‹€. 고둜 전체 μˆ˜ν–‰ νšŸμˆ˜λŠ” N + 100 이 λœλ‹€.
  • 그런데 N 이 컀지면 컀질 수둝 사싀 100번 μˆ˜ν–‰ν•˜λŠ” λ°˜λ³΅λ¬Έμ€ μˆ˜ν–‰ μ‹œκ°„μ—μ„œ μ°¨μ§€ν•˜λŠ” 비쀑이 μ€„μ–΄λ“€κ²Œ λœλ‹€. λ”°λΌμ„œ κΆκ·Ήμ μœΌλ‘œλŠ” 이 μ•Œκ³ λ¦¬μ¦˜μ˜ μˆ˜ν–‰ μ‹œκ°„μ„ N 이라고 μ“΄λ‹€.

πŸ” μ„ ν˜• μ‹œκ°„ μ•Œκ³ λ¦¬μ¦˜

λ‹€μ΄μ–΄νŠΈ ν˜„ν™© νŒŒμ•…: 이동 평균 κ³„μ‚°ν•˜κΈ°
이동 평균(moving average)은 μ‹œκ°„μ— 따라 λ³€ν™”ν•˜λŠ” 값듀을 κ΄€μ°°ν•  λ•Œ μœ μš©ν•˜κ²Œ μ‚¬μš©ν•  수 μžˆλŠ” 톡계적 기쀀이닀. N개의 μΈ‘μ •μΉ˜κ°€ μ£Όμ–΄μ§ˆ λ•Œ 맀달 M달 κ°„μ˜ 이동 평균을 κ³„μ‚°ν•˜λŠ” ν”„λ‘œκ·Έλž¨μ€ μ–΄λ–»κ²Œ μ§œμ•Ό ν• κΉŒ?

  • 각 μœ„μΉ˜μ—μ„œ μ§€λ‚œ M개 μΈ‘μ •μΉ˜μ˜ 합을 κ΅¬ν•˜κ³ , 이λ₯Ό M으둜 λ‚˜λˆˆλ‹€.
private static double[] movingAverage(double[] A, int M) { int N = A.length; double[] ret = new double[N]; int retIdx = 0; for (int i = M-1; i < N; i++) { double partialSum = 0; for (int j = 0; j < M; j++) partialSum += A[i-j]; ret[retIdx++] = partialSum/M; } return ret; }
  • μ΄λŠ” κ°„λ‹¨ν•˜κ²Œ 두 개의 for문을 μ‚¬μš©ν•˜λŠ” μ½”λ“œλ‘œ κ΅¬ν˜„ν•  수 μžˆλ‹€.

    • 즉 두 개의 for문에 μ˜ν•΄ μ§€λ°°λœλ‹€.
  • 이 μ½”λ“œμ˜ μˆ˜ν–‰ μ‹œκ°„μ„ μ’€ 더 μ€„μ΄λŠ” 방법은 μ—†μ„κΉŒ?

μ€‘μš”ν•œ μ•„μ΄λ””μ–΄λŠ” μ€‘λ³΅λœ 계산을 μ—†μ• λŠ” 것이닀.

μΈ‘μ •μΉ˜κ°€ Mκ°œλŠ” λ˜μ–΄μ•Ό 이동 평균을 계산할 수 μžˆμœΌλ‹ˆ, νƒœμ–΄λ‚œ 이후 M-1일뢀터 이동 평균을 계산할 수 μžˆλ‹€.

  • μ•„λž˜ ν‘œμ—μ„œ M-1일의 이동 평균과 M일의 이동 평균에 ν¬ν•¨λ˜λŠ” μˆ«μžλ“€μ„ μ°Ύμ•„λ³Έλ‹€.
λ‚ μ§œ 0 1 2 3 4 ... M-1 M M+1
λͺΈλ¬΄κ²Œ 3.5 3.5 3.5 3.6 3.5 ... 80.2 80.1 80.3
  • 0일과 M일의 λͺΈλ¬΄κ²Œλ₯Ό μ œμ™Έν•˜λ©΄ μ „λΆ€ κ²ΉμΉœλ‹€λŠ” 것을 확인할 수 μžˆλ‹€.
  • κ·Έλ ‡λ‹€λ©΄ μΈ‘μ •ν•œ λͺΈλ¬΄κ²Œμ˜ 합을 일일이 ꡬ할 ν•„μš” 없이 M-1일에 κ΅¬ν–ˆλ˜ λͺΈλ¬΄κ²Œμ˜ ν•©μ—μ„œ 0일째에 μΈ‘μ •ν•œ λͺΈλ¬΄κ²Œλ₯Ό λΉΌκ³  M일째에 μΈ‘μ •ν•œ λͺΈλ¬΄κ²Œλ₯Ό λ”ν•˜λ©΄ λ˜μ§€ μ•Šμ„κΉŒ?
private static double[] movingAverage2(double[] A, int M) { int N = A.length; double[] ret = new double[N]; int retIdx = 0; double partialSum = 0; for (int i = 0; i < M-1; i++) partialSum += A[i]; for (int i = M-1; i < N; i++) { partialSum += A[i]; ret[retIdx++] = partialSum/M; partialSum -= A[i-M+1]; } return ret; }
  • ν•˜λ‚˜λ‘œ λ¬Άμ—¬μžˆλ˜ 이쀑 for문을 뢄리해 반볡문의 μˆ˜ν–‰ 횟수λ₯Ό ν™• μ€„μ˜€λ‹€.
  • μˆ˜ν–‰ μ‹œκ°„μ€ N에 μ •λΉ„λ‘€ν•˜κ²Œ 되고, κ·Έλž˜ν”„λ‘œ 그렀보면 μ •ν™•νžˆ 직선이 λœλ‹€.

    • μ΄λŸ¬ν•œ μ•Œκ³ λ¦¬μ¦˜μ„ μ„ ν˜• μ‹œκ°„(linear time) μ•Œκ³ λ¦¬μ¦˜μ΄λΌκ³  ν•œλ‹€.
    • 이런 μ•Œκ³ λ¦¬μ¦˜μ΄ λŒ€κ°œ κ°€μž₯ 쒋은 μ•Œκ³ λ¦¬μ¦˜μΈ κ²½μš°κ°€ λ§Žλ‹€. μ£Όμ–΄μ§„ μž…λ ₯을 μ΅œμ†Œν•œ ν•œ λ²ˆμ”© 쳐닀보기라도 ν•˜λ €λ©΄ μ„ ν˜• μ‹œκ°„μ΄ 걸릴 μˆ˜λ°–μ— μ—†κΈ° λ•Œλ¬Έμ΄λ‹€!

πŸ” μ„ ν˜• μ΄ν•˜ μ•Œκ³ λ¦¬μ¦˜

μ„±ν˜• μ „ 사진 μ°ΎκΈ°
μ–΄λ–€ 문제 건 μž…λ ₯된 자료λ₯Ό λͺ¨λ‘ ν•œ 번 ν›‘λŠ”λ°λŠ” μž…λ ₯의 크기에 λΉ„λ‘€ν•˜λŠ” μ‹œκ°„, 즉 μ„ ν˜• μ‹œκ°„μ΄ κ±Έλ¦°λ‹€. 그런데 μ„ ν˜• μ΄ν•˜ μ•Œκ³ λ¦¬μ¦˜μ€ 그만큼의 μ‹œκ°„λ„ 걸리지 μ•ŠλŠ”λ‹€λŠ” 의미인데, μ–΄λ–»κ²Œ κ°€λŠ₯ν• κΉŒ? μž…λ ₯으둜 μ£Όμ–΄μ§„ μžλ£Œμ— λŒ€ν•΄ μš°λ¦¬κ°€ 미리 μ•Œκ³  μžˆλŠ” 지식을 ν™œμš©ν•  수 μžˆλ‹€λ©΄ κ°€λŠ₯ν•΄μ§„λ‹€.

예λ₯Ό λ“€μ–΄, μ–΄λ–€ μ—°μ˜ˆμΈ Aꡰ의 μ½” μ„±ν˜• μ „ 고등학ꡐ 사진이 κ³΅κ°œλ˜μ—ˆλ‹€. 남듀 λͺ°λž˜ Aꡰ의 팬인 μ €λŠ” Aꡰ이 λŒ€μ²΄ μ–Έμ œ μ„±ν˜•μ„ ν–ˆλŠ”μ§€ μ•Œκ³  μ‹Άμ–΄ κ²€μƒ‰μ—”μ§„μœΌλ‘œ Aꡰ의 사진 10만 μž₯을 μ°Ύμ•„ 이듀을 촬영 λ‚ μ§œ 순으둜 μ •λ ¬ν–ˆλ‹€. 그럼 Aꡰ이 μ–Έμ œ μ„±ν˜•ν–ˆλŠ”μ§€λ₯Ό κ°€λŠ₯ν•œ ν•œ μ •ν™•ν•˜κ²Œ μ•Œλ €λ©΄ λŒ€μ²΄ λͺ‡ μž₯의 사진을 확인해야 ν• κΉŒ?

  • 10만μž₯의 사진을 λͺ¨λ‘ λ³΄λŠ” 것은 μ‹œκ°„ λ‚­λΉ„μ΄λ―€λ‘œ, 남은 사진듀을 항상 절반으둜 λ‚˜λˆ  κ°€μš΄λ° μžˆλŠ” 사진을 λ³΄λŠ” 것이닀.

    • λ¨Όμ € κ°€μš΄λ° μžˆλŠ” 5만 번째 사진을 ν™•μΈν–ˆμ„λ•Œ, μ½”λ₯Ό μ„±ν˜•ν•˜μ§€ μ•Šμ€ μƒνƒœλΌλ©΄ 이 μ „μ˜ 사진은 λ³Ό ν•„μš”κ°€ μ—†λ‹€. λ‹Ήμ—°νžˆ μ„±ν˜•μ„ ν•˜μ§€ μ•Šμ€ μƒνƒœμ˜ 사진듀일 κ²ƒμ΄λ‹ˆκΉŒ!
    • μ΄λ‘œμ„œ 확인해야 ν•  사진이 5만μž₯으둜 μ€„μ—ˆκ³ , λ‹€μ‹œ κ·Έ 쀑 κ°€μš΄λ° 사진을 확인해 μœ„μ˜ 과정을 λ™μΌν•˜κ²Œ κ±°μΉœλ‹€.
    • 확인할 λ•Œλ§ˆλ‹€ 남은 μž₯μˆ˜κ°€ λŒ€λž΅ 절반으둜 μ€€λ‹€λ©΄, 총 λͺ‡ μž₯의 사진을 확인해야 ν• κΉŒ?
ν™•μΈν•œ μ‚¬μ§„μ˜ 수 0 1 2 ... 9 10 11 12 13
남은 사진 100,000 50,000 25,000 ... 195 97 48 24 12

μœ„ ν‘œλŠ” ν™•μΈν•˜λŠ” μ‚¬μ§„μ˜ μˆ˜κ°€ 증가함에 따라 남은 μ‚¬μ§„μ˜ μˆ˜κ°€ μ–΄λ–»κ²Œ μ€„μ–΄λ“œλŠ”μ§€λ₯Ό 보여쀀닀. λŒ€λž΅ 17μž₯의 μ‚¬μ§„λ§Œ ν™•μΈν•˜λ©΄ μ„±ν˜•ν•œ μ‹œμ μ„ μ°Ύμ•„λ‚Ό 수 μžˆλ‹€.

  • 이λ₯Ό 봐야 ν•˜λŠ” μ‚¬μ§„μ˜ μž₯수 N에 λŒ€ν•΄ ν‘œν˜„ν•˜κ²Œ 되면, 맀번 μ ˆλ°˜μ”© λ‚˜λˆ„λ‹ˆ 밑이 2인 둜그 log2log_2λ₯Ό μ‚¬μš©ν•˜λ©΄ 되고, λ”°λΌμ„œ λŒ€λž΅ logNlogN이 λœλ‹€.
  • loglogλŠ” ꡉμž₯히 느리게 μ¦κ°€ν•˜λŠ” ν•¨μˆ˜μ΄λ‹€. 이와 같이 μž…λ ₯의 크기가 μ»€μ§€λŠ” 것보닀 μˆ˜ν–‰ μ‹œκ°„μ΄ 느리게 μ¦κ°€ν•˜λŠ” μ•Œκ³ λ¦¬μ¦˜λ“€μ„ μ„ ν˜• μ΄ν•˜ μ‹œκ°„(sublinear time) μ•Œκ³ λ¦¬μ¦˜μ΄λΌκ³  ν•œλ‹€.

이진 탐색
방금 μ „ μ˜ˆμ œμ—μ„œ μ‚¬μš©ν•œ μ•Œκ³ λ¦¬μ¦˜μ„ 이진 탐색(binary search)라고 ν•œλ‹€.

binsearch(A[],x) = μ˜€λ¦„μ°¨μˆœμœΌλ‘œ μ •λ ¬λœ λ°°μ—΄ A[] 와 μ°Ύκ³  싢은 κ°’ x κ°€ μ£Όμ–΄μ§ˆ λ•Œ A[i-1] < x <= A[i] 인 i λ₯Ό λ°˜ν™˜ν•œλ‹€. μ΄λ•Œ A[-1] = -∞ , A[N] = ∞ 둜 κ°€μ •ν•œλ‹€.

  • μ‰½κ²Œ μƒκ°ν•΄μ„œ, λ°°μ—΄ A[] μ—μ„œ x λ₯Ό μ‚½μž…ν•  수 μžˆλŠ” μœ„μΉ˜ 쀑 κ°€μž₯ μ•žμ— μžˆλŠ” 것을 λ°˜ν™˜ν•˜λŠ” ν•¨μˆ˜λΌκ³  μƒκ°ν•˜λ©΄ λœλ‹€. λŒ€κ°œμ˜ λ°°μ—΄μ΄λ‚˜ 리슀트 κ΅¬ν˜„μ—μ„œ i 번째 μœ„μΉ˜μ— μƒˆ μ›μ†Œλ₯Ό μ‚½μž…ν•œλ‹€ = i λ²ˆμ§Έμ™€ κ·Έ μ΄ν›„μ˜ μ›μ†Œλ“€μ„ λ’€λ‘œ ν•œ μΉΈμ”© λ°€μ–΄λ‚΄κ³  듀어간닀와 λ™μΌν•œ μ˜λ―Έμ΄λ‹€.

    • λ”°λΌμ„œ A[] 에 x κ°€ μ‘΄μž¬ν•œλŠ 경우 이 ν•¨μˆ˜λŠ” 첫 번째 x 의 μœ„μΉ˜λ₯Ό λ°˜ν™˜ν•˜κ³ , μ—†λŠ” 경우 x 보닀 큰 첫 번째 μ›μ†Œλ₯Ό λ°˜ν™˜ν•œλ‹€.

κ·Έλž˜λ„ μ„ ν˜• μ‹œκ°„ μ•„λ‹Œκ°€μš”?
그런데 binsearch() 에 μž…λ ₯λ˜λŠ” 배열을 λ§Œλ“€κΈ° μœ„ν•΄μ„œλŠ” κ²°κ΅­ λͺ¨λ“  사진을 λ³΄λ©΄μ„œ μ„±ν˜• 이전인지 μ—¬λΆ€λ₯Ό νŒλ‹¨ν•΄μ•Ό ν•œλ‹€. κ²Œλ‹€κ°€ κ·Έ μ „μ—” λͺ¨λ“  사진을 λ°›μ•„ μ‹œκ°„ 순으둜 μ •λ ¬κΉŒμ§€ ν•΄μ•Ό ν•œλ‹€. λ”°λΌμ„œ μ „μ²΄λŠ” μ„ ν˜• μ‹œκ°„μ΄ κ±Έλ¦¬λŠ” 게 μ•„λ‹Œκ°€ ν•˜λŠ” 의문이 λ“ λ‹€. ν•˜μ§€λ§Œ μ΄λ ‡κ²Œ λΆ„μ„ν•˜μ§€ μ•ŠλŠ” μ΄μœ λŠ” λ‹€μŒκ³Ό κ°™λ‹€.

  1. A[] λ₯Ό μ‹€μ œλ‘œ κ³„μ‚°ν•΄μ„œ κ°€μ§€κ³  μžˆμ„ ν•„μš”κ°€ μ—†λ‹€. 사싀은 μž…λ ₯ 배열을 λ„˜κ²¨μ€€λ‹€ν•΄λ„, 이진 탐색 μ•Œκ³ λ¦¬μ¦˜ λ‚΄λΆ€μ—μ„œλŠ” κ·Έ 쀑 λͺ‡ 개 보지도 μ•Šμ„ 것이닀. λ”°λΌμ„œ 이듀을 미리 계산할 것이 μ•„λ‹ˆλΌ, κ°€μš΄λ° μžˆλŠ” 것듀에 λŒ€ν•΄μ„œλ§Œ ν•„μš”ν•  λ•Œ 계산(μ„±ν˜• μ—¬λΆ€λ₯Ό νŒλ‹¨)ν•˜λ©΄ λœλ‹€.

    • binsearch() 에 A[] λ₯Ό 인자둜 λ„˜κΈ°λŠ” 것이 μ•„λ‹Œ i κ°€ μ£Όμ–΄μ§ˆ λ•Œ A[i] 의 값을 직접 κ³„μ‚°ν•˜λŠ” 콜백 ν•¨μˆ˜λ₯Ό μ œκ³΅ν•œλ‹€κ±°λ‚˜ ν•˜λŠ” λ°©λ²•μœΌλ‘œ ν•΄κ²° κ°€λŠ₯ν•˜λ‹€.
  2. 사진을 λ‹€μš΄λ°›κ³  μ •λ ¬ν•˜λŠ” 과정은 μ‹€μ œλ‘œ μ„±ν˜• μ „ 사진을 μ°ΎλŠ” μž‘μ—…κ³ΌλŠ” λ³„κ°œμ΄λ‹€. λ§Œμ•½ Aꡰ이 μ½”λΏλ§Œ μ•„λ‹ˆλΌ ν„±κΉŒμ§€λ„ μ„±ν˜•μ„ ν–ˆλ‹€κ³  ν•˜λ©΄, 이미 ν•œ 번 λ°›μ•„μ„œ μ •λ ¬ν•΄λ‘” 사진이 있으면 λ‹€μ‹œ 17μž₯의 μ‚¬μ§„λ§Œ ν™•μΈν•΄μ„œ μ–Έμ œ ν„± μ„±ν˜•μ„ ν–ˆλŠ”μ§€ μ•Œ 수 μžˆμ„ 것이닀.

κ΅¬ν˜„
이진 탐색을 μ •ν™•ν•˜κ²Œ κ΅¬ν˜„ν•˜λŠ” 것은 맀우 κΉŒλ‹€λ‘­λ‹€. μ΄λŠ” μ•Œκ³ λ¦¬μ¦˜μ˜ 정당성을 증λͺ…ν•˜λŠ” 방법을 λ‹€λ£° λ•Œ λ‹€μ‹œ μ–ΈκΈ‰ν•œλ‹€.

πŸ” μ§€μˆ˜ μ‹œκ°„ μ•Œκ³ λ¦¬μ¦˜

λ‹€ν•­ μ‹œκ°„ μ•Œκ³ λ¦¬μ¦˜
"반볡문의 μˆ˜ν–‰ 횟수λ₯Ό μž…λ ₯ 크기의 λ‹€ν•­μ‹μœΌλ‘œ ν‘œν˜„ν•  수 μžˆλŠ” μ•Œκ³ λ¦¬μ¦˜"듀을 λ‹€ν•­ μ‹œκ°„ μ•Œκ³ λ¦¬μ¦˜μ΄λΌκ³  ν•œλ‹€.

  • λ‹€ν•­ μ‹œκ°„μ΄λΌλŠ” ν•˜λ‚˜μ˜ λΆ„λ₯˜μ— ν¬ν•¨λ˜λŠ” μ•Œκ³ λ¦¬μ¦˜ κ°„μ—λŠ” μ—„μ²­λ‚˜κ²Œ 큰 μ‹œκ°„ 차이가 λ‚  수 μžˆλ‹€. (λ‹€ν•­μ‹μ˜ 포함 λ²”μ£Όκ°€ 맀우 크기 λ•Œλ¬Έ)
  • λ‹€ν•­ μ‹œκ°„λ³΄λ‹€ λ”λ”μš± 였랜 μ‹œκ°„μ΄ κ±Έλ¦¬λŠ” μ•Œκ³ λ¦¬μ¦˜λ“€μ΄ μžˆμ–΄ λ‹€ν•­ μ‹œκ°„ μ•Œκ³ λ¦¬μ¦˜μ„ λ¬Άμ—ˆλ‹€.

μ•ŒλŸ¬μ§€κ°€ μ‹¬ν•œ μΉœκ΅¬λ“€
집듀이에 Nλͺ…μ˜ 친ꡬλ₯Ό μ΄ˆλŒ€ν•˜λ €κ³  ν•œλ‹€. ν•  쀄 μ•„λŠ” Mκ°€μ§€ μŒμ‹ 쀑 무엇을 λŒ€μ ‘ν•΄μ•Ό ν• κΉŒλ₯Ό κ³ λ―Όν•˜λŠ”λ°, μΉœκ΅¬λ“€μ€ 각각 μ•ŒλŸ¬μ§€ λ•Œλ¬Έμ— λͺ» λ¨ΉλŠ” μŒμ‹λ“€μ΄ μžˆλ‹€. λ§Œλ“€ 쀄 μ•„λŠ” μŒμ‹μ˜ λͺ©λ‘κ³Ό, ν•΄λ‹Ή μŒμ‹μ„ λͺ» λ¨ΉλŠ” μΉœκ΅¬λ“€μ˜ λͺ©λ‘μ΄ μ£Όμ–΄μ§ˆ λ•Œ, 각 μΉœκ΅¬κ°€ 먹을 수 μžˆλŠ” μŒμ‹μ΄ μ΅œμ†Œ ν•˜λ‚˜μ”© 있으렀면 μ΅œμ†Œ λͺ‡ κ°€μ§€μ˜ μŒμ‹μ„ ν•΄μ•Ό ν• κΉŒ?

λͺ¨λ“  λ‹΅ 후보λ₯Ό ν‰κ°€ν•˜κΈ°
μ—¬λŸ¬ 개의 닡이 μ‘΄μž¬ν•  수 μžˆλ‹€. ν•˜μ§€λ§Œ μ΅œμ†Œ 개수의 닡을 κ΅¬ν•˜λ €κ³  ν•  λ•Œ, κ°€μž₯ κ°„λ‹¨ν•œ 방법은 λͺ¨λ“  닡을 일일이 κ³ λ €ν•΄ λ³΄λŠ” 것이닀.

  • λ§Œλ“€ 수 μžˆλŠ” μŒμ‹μ˜ λͺ¨λ“  λͺ©λ‘μ„ λ§Œλ“œλŠ” 과정은 μ—¬λŸ¬ 개의 κ²°μ •μœΌλ‘œ λ‚˜λˆ„λ©΄ μžμ—°μŠ€λŸ½λ‹€.
  • 첫 번째 μš”λ¦¬λ₯Ό λ§Œλ“€μ§€ 말지 κ²°μ •ν•˜κ³ , 두 번째 μš”λ¦¬λ₯Ό λ§Œλ“€μ§€ 말지λ₯Ό κ²°μ •ν•˜λŠ” 방식이닀. μ΄λ ‡κ²Œ μ μ§„μ μœΌλ‘œ κ²°μ •ν•˜λ‹€λ³΄λ©΄, λ§ˆμ§€λ§‰μ—λŠ” 쑴재 κ°€λŠ₯ν•œ λͺ¨λ“  λͺ©λ‘μ„ λ§Œλ‚  수 μžˆλ‹€.

    • 이제 κ°€μž₯ 적은 수의 λͺ©λ‘μ„ μ°ΎλŠ”λ‹€.

이런 μ•Œκ³ λ¦¬μ¦˜μ„ κ΅¬ν˜„ν•˜λŠ” κ°€μž₯ μ‰¬μš΄ 방법은 μž¬κ·€ ν˜ΈμΆœμ„ μ΄μš©ν•˜λŠ” 것이닀.

  • μ΄λ•Œ μž¬κ·€ ν•¨μˆ˜λŠ” ν•œ μƒνƒœλ₯Ό μž…λ ₯λ°›μ•„ 이 μƒνƒœ 밑에 달린 λͺ¨λ“  후보듀을 κ²€μ‚¬ν•˜κ³  이 쀑 κ°€μž₯ 쒋은 닡을 λ°˜ν™˜ν•˜λŠ” 역할을 ν•œλ‹€.
int INF = 987654321; int M; private static boolean canEverybodyEat(Stack<Integer> menu) { ... } private static int selectMenu(Stack<Integer> menu, int food) { if (food == M) { if (canEverybodyEat(menu)) return menu.length; return INF; } int ret = selectMenu(menu, food + 1); menu.push(food); ret = Math.min(ret, selectMenu(menu, food + 1)); menu.pop(); return ret; }

μ§€μˆ˜ μ‹œκ°„ μ•Œκ³ λ¦¬μ¦˜
μœ„ ν”„λ‘œκ·Έλž¨μ€ λͺ¨λ“  닡을 ν•œ λ²ˆμ”© λ‹€ ν™•μΈν•˜κΈ°μ—, 전체 κ±Έλ¦¬λŠ” μ‹œκ°„μ€ λ§Œλ“€ 수 μžˆλŠ” λ‹΅μ˜ μˆ˜μ— λΉ„λ‘€ν•˜κ²Œ λœλ‹€.

  • Mκ°€μ§€μ˜ μŒμ‹λ§ˆλ‹€ 두 선택지가 μžˆμ–΄ λ§Œλ“€ 수 μžˆλŠ” 닡은 λͺ¨λ‘ 2M2^M가지이닀.
  • 그리고 닡을 ν•˜λ‚˜ λ§Œλ“€ λ•Œλ§ˆλ‹€ canEverybodyEat() λ₯Ό μˆ˜ν–‰ν•΄ 이 μ•Œκ³ λ¦¬μ¦˜μ˜ μˆ˜ν–‰ μ‹œκ°„μ€ 2M2^M에 canEverybodyEat() 의 μˆ˜ν–‰ μ‹œκ°„μ„ κ³±ν•œ 것이 λœλ‹€.
  • 2M2^Mκ³Ό 같은 μ§€μˆ˜ ν•¨μˆ˜λŠ” μ•Œκ³ λ¦¬μ¦˜μ˜ 전체 μˆ˜ν–‰ μ‹œκ°„μ— μ—„μ²­λ‚œ 영ν–₯을 λ―ΈμΉœλ‹€. 이와 같이 N이 ν•˜λ‚˜ 증가할 λ•Œλ§ˆλ‹€ κ±Έλ¦¬λŠ” μ‹œκ°„μ΄ 배둜 μ¦κ°€ν•˜λŠ” μ•Œκ³ λ¦¬μ¦˜λ“€μ€ μ§€μˆ˜ μ‹œκ°„(exponential time)에 λ™μž‘ν•œλ‹€κ³  ν•œλ‹€.

    • κ°€μž₯ 큰 μˆ˜ν–‰ μ‹œκ°„ 쀑 ν•˜λ‚˜μ΄λ‹€.

μ†ŒμΈμˆ˜ λΆ„ν•΄μ˜ μˆ˜ν–‰ μ‹œκ°„
μž…λ ₯으둜 μ£Όμ–΄μ§€λŠ” 숫자의 κ°œμˆ˜κ°€ μ•„λ‹ˆλΌ κ·Έ 크기에 따라 μˆ˜ν–‰ μ‹œκ°„μ΄ λ‹¬λΌμ§€λŠ” μ•Œκ³ λ¦¬μ¦˜λ“€ λ˜ν•œ μ§€μˆ˜ μˆ˜ν–‰ μ‹œκ°„μ„ κ°€μ§ˆ 수 μžˆλ‹€.

  • μžμ—°μˆ˜ N이 μ£Όμ–΄μ§ˆ λ•Œ N의 μ†ŒμΈμˆ˜ λΆ„ν•΄ κ²°κ³Όλ₯Ό λ°˜ν™˜ν•˜λŠ” κ°„λ‹¨ν•œ μ•Œκ³ λ¦¬μ¦˜μ΄ μžˆλ‹€.
  • 이 μ•Œκ³ λ¦¬μ¦˜μ€ N이 1이 될 λ•ŒκΉŒμ§€ κ°€λŠ₯ν•œ λͺ¨λ“  숫자둜 N을 λ‚˜λˆ λ³΄λŠ”λ°, μ£Όμ–΄μ§„ 수 N이 μ†Œμˆ˜μΈ 경우 반볡문이 κ°€μž₯ 많이 μ‹€ν–‰λœλ‹€.

결과적으둜 반볡문의 μ‹€ν–‰ νšŸμˆ˜λŠ” N - 1이 λ˜μ–΄, μ‹€ν–‰ νšŸμˆ˜κ°€ λŒ€λž΅ N에 λΉ„λ‘€ν•΄ μ΅œμ•…μ˜ 경우 μ„ ν˜• μ‹œκ°„μ΄ κ±Έλ¦°λ‹€κ³  생각할 μˆ˜λ„ μžˆλ‹€.

이런 뢈일치λ₯Ό μ§κ΄€μ μœΌλ‘œ μ΄ν•΄ν•˜κΈ° μœ„ν•΄ μ•Œκ³ λ¦¬μ¦˜μ˜ μˆ˜ν–‰ μ‹œκ°„κ³Ό μž…λ ₯이 λ©”λͺ¨λ¦¬μ—μ„œ μ°¨μ§€ν•˜λŠ” κ³΅κ°„μ˜ 관계λ₯Ό μƒκ°ν•΄λ³΄μž.

  • 이진 탐색, 이동 평균 계산 λ“± μ§€κΈˆκΉŒμ§€ 닀룬 μ•Œκ³ λ¦¬μ¦˜μ—μ„œλŠ” μž…λ ₯의 값듀이 일정 λ²”μœ„ 내에 μžˆλ‹€κ³  μ–΄λ ΅μ§€ μ•Šκ²Œ κ°€μ •ν•  수 μžˆλ‹€.

    • 이 경우 μž…λ ₯의 κ°œμˆ˜μ™€ λ©”λͺ¨λ¦¬μ—μ„œ μ°¨μ§€ν•˜λŠ” 곡간이 μ§μ ‘μ μœΌλ‘œ λΉ„λ‘€ν•œλ‹€.
  • 반면, μ†ŒμΈμˆ˜ λΆ„ν•΄ λ¬Έμ œμ—μ„œλŠ” μž…λ ₯으둜 μ£Όμ–΄μ§€λŠ” μˆ«μžκ°€ μ•Œκ³ λ¦¬μ¦˜μ˜ λ™μž‘μ— 직접적인 영ν–₯을 미쳐, μˆ«μžκ°€ νŠΉμ • λ²”μœ„ μ•ˆμ— μžˆλ‹€κ³  κ°€μ •ν•  수 μ—†λ‹€.

    • μž…λ ₯의 값이 컀질수둝 숫자λ₯Ό μ €μž₯ν•˜λŠ”λ° ν•„μš”ν•œ λ©”λͺ¨λ¦¬μ˜ 곡간도 증가할 것이닀.
    • μ΄λ•Œ μž…λ ₯이 μ°¨μ§€ν•˜λŠ” λΉ„νŠΈμ˜ μˆ˜μ— 따라 μˆ˜ν–‰ μ‹œκ°„μ΄ μ¦κ°€ν•œλ‹€κ³  μƒκ°ν•˜λ©΄ μ•„κΉŒμ˜ 뢈일치λ₯Ό μ§κ΄€μ μœΌλ‘œ μ„€λͺ…ν•  수 μžˆλ‹€.

πŸ” μ‹œκ°„ λ³΅μž‘λ„

πŸ” μˆ˜ν–‰ μ‹œκ°„ μ–΄λ¦Όμ§μž‘ν•˜κΈ°

πŸ” 계산 λ³΅μž‘λ„ 클래슀: P, NP, NP-μ™„λΉ„

πŸ“• μ°Έκ³ 

ν”„λ‘œκ·Έλž˜λ° λŒ€νšŒμ—μ„œ λ°°μš°λŠ” μ•Œκ³ λ¦¬μ¦˜ 문제 ν•΄κ²° μ „λž΅ - κ΅¬μ’…λ§Œ

@Seongukbaek
배우고 μ •λ¦¬ν•˜κ³  κ³΅μœ ν•˜λŠ” λŒ€ν•™μƒ λ°±μ„±μš±μž…λ‹ˆλ‹€ πŸ˜€